/*
 * @Author: 缄默
 * @Date: 2021-11-16 15:14:45
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-16 19:14:50
 */

//换钱的最少货币数

#include <iostream>
#include <vector>

using namespace std;

int minCoins(vector<int>& arr, int aim);
int process(vector<int>& arr, int i, int rest);
int minCoins2(vector<int>& arr, int aim);

int main() {

    vector<int> arr({5, 2, 3});
    int aim = 20;
    cout << minCoins(arr, aim) << endl;
    cout << minCoins2(arr, aim) << endl;
    return 0;
}

//利用递归求解
int minCoins(vector<int>& arr, int aim) {
    if (arr.size() == 0 || aim < 0) return -1;
    return process(arr, 0, aim);
}

//货币数组， 第一张货币， 剩余钱数
int process(vector<int>& arr, int level, int rest) {
    //退出递归的条件 没有纸币可选
    //判断余额是否是0
    if (level == arr.size()) return rest == 0 ? 0 : -1;
    int res = -1;

    //依次测试纸币用多少张 用递归和level去逐个判断
    for (int i = 0; i * arr[level] <= rest; i++) {
        //先判断是否能够找开
        int count = process(arr, level +  1, rest - i * arr[level]);
        //能够找开就判断之前的res和现在的零钱数谁多
        if (count != -1) {
            res = res == -1 ? count + i : (res < count + i ? res : count + i);
        }
    }
    return res;
}

//利用动态优化求解
int minCoins2(vector<int>& arr, int aim) {
    if (arr.size() == 0 || aim < 0) return -1;
    vector<vector<int>> dp(arr.size() + 1,vector<int>(aim + 1, 0));
    for (int col = 1; col <= aim; col++) {
        dp[arr.size()][col] = -1;
    }
    //通过最后一行进行加法运算
    for (int i = arr.size() - 1; i>= 0; i--) {
        for (int rest = 0; rest <= aim; rest++) {
            dp[i][rest] = -1;
            if (dp[i + 1][rest] != -1) {
                dp[i][rest] = dp[i + 1][rest];
            }
            if (rest - arr[i] >= 0 && dp[i][rest - arr[i]] != -1) {
                if (dp[i][rest] == -1) {
                    dp[i][rest] = dp[i][rest - arr[i]] + 1;
                }
                else {
                    dp[i][rest] = dp[i][rest] < (dp[i][rest - arr[i]] + 1) ? dp[i][rest] : (dp[i][rest - arr[i]] + 1);
                }
            }
        }
    }
    return dp[0][aim];
}

